1994
212 777
214427795 655419475 306451873 240189637 317064335 656836591 211836038 331411539 711142311 979144704 118970756 280310311 481940689 941496815 216252506 744919173 205038904 1170550 312016959 315889728 180693178 460466213 506009689 45261122 381457002 280893408 468665415 63145738 263847183 877557087 539169432 325296425 323882916 352759725 763378514 990383556 169561558 358033834 14808172 878962709 971897993 500779657 560237139 33242346 468292691 573707858 210893417 114646309 938166783 651210337 378195329 634300986 580240652 576097765 547704933 202508980 211500 643145826 783812176 29084336 692515781 662846000 375186293 99280479 74042483 122843385 141578102 144871049 371424644 933204031 423072237 155258629 360811386 364586963 124839142 477280066 215881869 970820191 861231459 938607298 645007143 782436830 463688151 295354777 169708134 14004766 259677868 986388210 921629341 634230085 182639805 225572746 435936211 388850249 167268316 461741619 337503298 265203063 146740045 204255315 562415321 390031085 849824329 946140770 713662395 310021919 618424445 841541744 122697406 751930710 424946824 947501212 454980077 125277228 74661504 866178462 484942343 574964753 552196718 694113598 496310013 79717833 434418381 572814042 622239864 844610284 112967951 450237412 941305424 597084773 162892824 584943714 840305430 888871668 902539457 19108717 975660683 815310252 308270678 466835890 217166887 997283957 731862296 137123316 694376851 523733643 753951933 942563207 793211695 800243453 631068907 501769943 863479437 629302063 101743040 361262559 91078387 652586328 896936013 93392051 479073758 13126917 680191766 102243830 981167482 371314068 510243988 862077796 45905706 983793850 135119795 105323594 751540742 684978430 880748116 668715017 339516248 265619003 731653068 483957399 339857182 729561634 849394019 240593149 26399372 477583541 987836630 995862490 571051655 919744718 568348886 144180702 631753770 115835542 433764743 172936272 956138821 379150350 416283394 199203721 912295129 433908105 811420627 434426743 16703389 394020400 273889659 864210971 94480508 679140477 820074223 336479755 105043733 838931136 49216279 727034608 48281146 361748893 231026512 370891273 562168433 543349900 417448427 700509351 331072630 454069848 256628396 369167023 710014391 582900129 276974923 804068123 1566422 59885402 570377206 60016761 844560427 385191755 764627917 552805738 969913920 688193680 793460581 953877284 945857107 53806104 582602566 304946161 534747863 612588327 151568493 500606382 318342131 967492052 542938827 672151629 399343105 355093900 335138243 105513555 115189776 661653901 482481328 346621787 479011427 287496044 231052637 995058833 253524720 369493903 32083595 804372279 919060962 350200244 528211054 846110499 478697496 445291368 313138480 250959679 477541283 911433361 690798957 438834184 265559116 222531557 94290102 937036304 287796236 67545968 791038478 109411453 568878481 911430930 107226736 135573895 587973823 994151679 927835462 859858173 260933933 83434045 922742515 991605441 298454180 670218025 137339211 383777095 560645540 719636466 523414550 24717338 623392223 817517341 277540752 664357464 918984380 7339007 939170028 408662833 701322197 557338950 41466060 371555435 996763001 234095473 865450443 49688289 434944299 319316819 128229107 688810239 73282081 298209428 750751815 473732424 762768326 448809008 561426747 22526161 756652600 339572470 60240182 896915907 632276682 638504970 438705687 805572060 845875331 68896099 279661741 121592559 757412510 801879118 165867326 605781855 451718408 871356905 440055809 952066728 129606886 226380201 149310372 820616663 319246604 559799764 184250822 554102284 325986950 431787016 307194750 53254911 586810643 88233906 77323730 557769081 320644005 608658584 309861953 190680534 88269026 854888272 685459258 404305546 211379622 661281734 942415010 781872793 931569023 434356154 119983187 30004252 973974320 726144319 305680023 732148931 563506990 67990334 821052593 192516174 506034726 707350001 323767636 384825107 533769077 745166184 370899754 879731836 756408238 244748295 885479246 313532805 214767896 891799302 250311634 184343874 178120237 751092976 59156538 319091031 437585437 46224932 463809023 848915070 408389449 368787799 899251470 465878277 216184776 46181904 85518918 463879501 695974373 766955819 917213694 796209740 913077918 856342871 51612796 868244492 385571879 843286424 120049791 61739050 855312485 439010245 759898549 321455703 29228916 824493323 734340422 287865563 486729762 963113064 110962760 778666253 839415921 938291505 343100488 315502556 771276825 50948492 542413255 315721289 323702019 461644023 540330682 247385578 27335119 664470207 646935818 112301417 847312975 641505418 933074194 919175427 170564106 6093006 162823716 513217290 44852410 805306711 779327748 220374628 492233422 60535749 336253035 156576521 476766697 195066379 452246405 333210248 325611873 82143986 504833652 465531523 177955009 846891156 987090635 547570478 351078983 963357409 75552787 130197460 961409894 325136413 60404297 33809746 97735494 577261920 244072030 382030490 534974271 979790612 982697142 156462898 658794338 705066363 631507370 938808242 696902384 72948519 236383238 794767946 617832672 365790080 408936843 684950329 753901661 545985346 884445550 95763287 574975302 405147900 391545047 436257420 267943085 734132625 868815715 999597654 120965976 694501051 761252771 76120648 246009923 639161731 58677147 713040517 664147228 221101770 618330435 878429257 618131142 598683588 984565513 431399008 297574359 166203000 250420814 165916589 547516697 384267329 150107108 4235685 160992268 62734928 253192342 616603345 819787619 296020007 868081569 229819728 255323523 134257695 487451955 152564050 462509319 926710755 171337459 747048350 868810046 815894771 66922616 186461709 799844523 184438050 135379920 161218572 518229893 3047705 900503035 785275166 697644597 156545234 829027694 3878232 235338202 367597597 797320337 294961636 917247176 695469342 244753473 843531646 168499460 238841549 182669391 322003706 979585738 811446644 922804222 208836540 687623944 758264629 178233481 251057726 23712736 589460098 945540507 990880910 62410538 188079267 245929429 191021261 39634671 326725684 227593035 201928625 145142767 143153059 353360903 228012291 475418140 548387254 39485061 339893794 954196253 66448388 421537845 227122815 638784716 558284663 187481597 188968991 510557624 202707152 230372532 852331548 17021348 785956131 674609576 650610980 394484742 18096214 426005785 791522296 77635721 191118247 303886524 454622703 490593675 341016099 786510904 708374896 858858656 446289712 101422508 68530811 529207565 972337412 925117479 107526433 435192909 317851435 444942383 438977032 897390736 322916101 249739835 272018664 364027703 743895109 498852153 471750928 159952730 750367091 743029513 672437217 823097922 507270251 842552063 872131922 636428783 375343836 508266085 778068587 144398738 580685002 524344055 739055050 630977044 29721357 878514533 807792161 688430734 461992912 354446292 531755701 4987087 596554002 664968285 293174753 428748762 786784552 5987213 862391697 414841956 681991993 77683940 755263432 636906330 557236161 385284950 12851482 250541657 39583503 188975053 531462962 355330612 887482310 342234532 522030925 280955762 255105376 72262445 533349054 475473614 377549478 483720237 401899368 61882293 803206201 997636187 80257607 396478667 22761741 969843172 669412839 303444582 234402024 421037034 848936171 483973394 761349352 314697472 817985160 458747915 904081914 262791600 5150983 889024966 615022435 74497781 42991686 506775656 265398587 375708865 592180792 291544141 962151149 997068408 247282016 399667331 439312825 213710707 963692890 222802764 553639219 253668223 58154323 348584096 867914689 69396315 660138636 973936296 247073056 405489469 235480794 873290308 294591711 761352014 659262761 171730822 135861474 22009897 88401397 448881205 176653280 757273440 306472911 62323787 858803174 749028855 618657246 622952056 240667347 426310887 103935579 264430748 267240666 770680220 496023316 328803920 237029635 56272504 963012074 725709662 453115305 868531022 220892499 714466373 293991165 68505575 648784088 925904566 517814146 527908481 614734744 985680409 212355727 404121674 414159555 24497161 805838032 64368105 596623905 171937492 683826885 658722806 372439177 602124796 736416066 307542909 651747946 874145464 748258285 217073280 240070725 140329075 461171140 241302130 944338224 952725324 355914132 107705020 914386773 165166229 901571203 272139579 495109233 287899477 231882886 856901824 910661717 129334470 676568811 949848463 345518441 730107095 212137169 587832801 675560740 617305770 790838187 829591138 457930901 383119639 37500354 131167411 977554141 767629096 186959536 32454121 707896242 364905627 731598309 42510092 892432350 420958307 381773093 772987289 286737342 649829160 388501255 618430977 105758660 262504898 629790072 230061096 680863990 848557505 17047094 360482278 914476908 60684264 495851862 623375241 456519893 728445102 971077567 116669521 829999347 496064700 397416365 272980211 91691546 172875633 893101870 875549719 687761845 683275105 79115944 602673882 714223810 158158545 672886609 700003661 639170129 962208317 823718838 133994740 629287944 73785555 475635253 852407623 325039266 828317942 730295682 948686900 206036587 599148219 513593638 832347803 391935942 583751791 439832571 889023185 902037415 13292815 26429105 67066142 247991834 882505934 882226253 147705407 256529594 152938899 751611045 425010148 538934074 799275896 221820133 830390067 293950944 510260556 455581708 785587523 597090309 514735890 829713776 500171682 846699158 96341120 730474294 18111696 172044950 277936001 140049115 733907650 217486746 372274355 392988590 268557151 880979531 939237354 509222739 518960390 84636392 43147947 805011009 273224967 55613377 41074866 467035205 866071589 10424253 979843692 113051901 296325914 194736853 229666174 303376478 814095635 73484950 189800764 278900527 826053168 184365731 852058418 986849676 787103750 925401905 194799007 923641187 57924636 204060554 721551861 119429882 348186737 689180810 809830235 836610919 206576116 786950949 556153643 642417942 264123147 277508831 189357940 632721992 162559501 431364178 170742137 543769486 645604808 204709292 144421935 920449106 220777979 367784238 73974979 229606734 694234589 585124270 838515986 735039250 222381205 932380438 234916400 125161602 388060095 247766243 963872994 359741782 943080941 885990566 381743139 639781529 673277732 287914118 999080355 620735275 207134555 647697853 420648003 233584191 164877568 916473111 491415706 753209821 171247986 807844726 103823219 863223137 787677063 428836432 569555021 209055226 243820552 622037039 354422746 719081772 768454193 378239280 264279680 637055823 456459314 200795013 685641435 601266701 955992496 108855283 425505849 744692456 954761796 158782037 799729436 689443249 199704059 536300055 89886140 594264850 100820436 889890491 127047810 745360134 265324613 214187607 95725710 413604699 15890359 143862805 435285555 599509559 530221829 974812851 888953717 889296016 666160129 74007809 293044882 12603058 262523375 317285989 655542390 996446909 536355848 127417178 327501637 938659621 26711033 301241324 377933013 620365104 833831009 21938238 57335089 11026300 166886230 60349700 982493463 957016694 40420577 552209417 253571707 794253539 938704765 522657451 449445634 696604251 956556444 861004378 266987144 839165897 620506402 656838428 778408346 282386925 434862056 338800652 646499837 479052762 343962170 388177878 824711973 897140088 46252122 307844413 809281215 900863491 238099963 901121430 185559847 779139210 838984902 557223754 822793714 490471025 46134488 12971096 376869990 724922863 402679618 214834384 111583229 69973137 931591816 966517081 185792230 61032373 664981283 745858476 62290564 425616656 401452031 580484374 205638125 569038633 6180605 494350586 96842860 165191643 875399538 45599053 172490239 186197719 279490214 390619928 999888857 472537631 895181911 773077242 546169057 660885132 433132339 149118372 922821170 278870602 502279521 223603290 67528601 648006487 178840313 143850872 3473434 654175239 654638215 714421995 770023020 882957187 60647308 800018100 395975032 61619781 867498237 291124073 125062878 175483037 627380674 311093940 465731439 743417647 596864824 891595218 826835892 832775539 801525680 179272212 795776102 17279540 786256110 782379361 458044660 574615570 531097258 419230387 816433152 43566592 590311186 694996629 381598178 469177798 890724166 582369196 827434787 875695232 112871899 264301867 520669955 1398557 787874137 35929437 722482677 751919328 848646845 948503071 542371870 202659811 824263672 969313122 455376345 227145103 323789421 146166702 521421877 266734886 89679735 956393626 739960693 710295609 403340001 187610965 799743887 644900658 872691564 160796448 625000622 361718732 97120588 749082578 185542577 745407381 261650091 341928531 773110441 828170867 47608869 574988065 706460510 285325084 152529227 872605390 289703371 72369052 340347680 442271359 266723998 943614931 195308703 380070511 480353209 344109045 3917619 54532202 842607284 424315656 339170620 639472210 183082328 684003177 536023697 812646558 140374053 90568519 701635321 375894230 43423949 117414695 443671729 843353112 566778039 205800030 764809449 764560790 974732669 811531674 5062215 397992214 120494446 452535642 292402530 371522416 550911501 149187185 294785352 5873940 830124688 127646343 374456824 855900289 360134241 598872728 347320041 977716943 202809249 537770867 480333698 886166054 717805472 69710395 567316895 487598149 461846886 138320618 207692819 678900476 377472558 386190537 124862752 765858482 375736805 601778938 868948736 902956256 417392559 638605038 561430112 799891 119547491 662087919 51551456 762127598 836295434 69321880 448643988 674157478 419989859 850038103 634969990 453268356 620574818 448156914 747685425 923044071 538690221 344268287 345260551 258909759 152085278 716605546 157680877 340308115 463419716 185696243 722088122 727122940 481668577 680965293 516100027 994021928 8237933 509284225 961147698 435054296 850969234 572656809 509653458 576978529 455023278 188928565 560461893 621410863 571302996 709522569 16641446 811589438 55902155 381558493 133466119 929407647 752098701 500651964 861396205 491998201 847674057 947398533 143245775 602074629 172952546 309922541 198102170 252650769 452076783 666996603 155201072 836078462 826810937 675371531 500187876 106755651 368722111 77978444 54598911 533177191 797365429 317978690 744981823 96397450 266108416 971128516 725365075 508288861 290749628 310094335 783382624 349289509 273196982 238947569 348521343 961251388 330978547 994987247 486629436 965888656 41180711 322031647 964857624 87753763 101282111 90123775 226375689 307862153 187448536 294729692 30596341 502723181 642968773 213714268 958071354 307449356 797983372 331968245 525398825 398075320 874388970 354235507 472275590 598904406 663461707 524272502 93467402 687502816 517766738 7845873 161345505 468489189 456481367 866337965 959087405 842950660 446084324 991795139 209910913 868913268 549286456 514217766 982883686 89150591 47094212 748236567 616213977 881541891 130151600 638161583 819168971 527689456 328144983 125454936 938898592 101577676 523889862 174041172 989887921 743391794 205871425 196621109 476082890 219845198 50440383 94478435 443544492 995680355 458557033 428180122 213616524 916645701 976299551 836123241 449880466 650123487 28353267 727857331 414781275 546787503 27431851 533167410 862985080 983578181 887560515 663920367 323284973 447455176 995829609 423831243 798535859 335699568 793672448 157259770 603267126 202179853 569975965 191107203 7628759 51762303 571010829 821053377 955914859 676004411 197116365 37776101 183311034 725272269 866457488 278197105 96216065 328062544 494713021 497989054 858314352 422422776 535898095 697544567 24485805 372293512 373319795 43359260 307226448 760862684 560414413 278659456 328738149 780636513 816124723 152612940 760010989 918594968 92931088 848682618 421257820 73608855 352910979 576762842 547715612 989331335 823295709 248916112 864196361 852560679 587999527 743888276 722261236 961078855 775611290 331825456 613738272 306833486 158574372 975583622 518980808 218158517 640827882 143633672 685700503 800477322 41255872 384112382 689800238 470755566 253449907 394618883 909347489 233033623 985237888 958409864 483669754 641568335 254494746 922450256 214777269 883417203 489410600 946318322 791150659 284662132 814400388 289837915 423159687 149725530 607366333 841127497 203539548 366200124 409815958 323373009 358477324 937072585 580113285 781824473 66875098 525665218 270663220 991524255 971652218 483202173 337528836 538939440 447521940 968438372 118995077 113230578 792252740 626768756 956980991 113537051 901037981 417490367 572905197 211590455 905132577 631008746 465443965 610520486 826690378 90932655 467619601 549720347 958228485 478550108 906873280 779912222 373403698 483616595 203689429 754899083 313896741 704543368 67542351 702539793 385157160 102408454 302113120 886963380 919304951 439221610 889559791 63230284 626999874 5013094 215436054 340233732 750062126 458950464 383753636 400576219 852003541 957574224 39567259 358382630 856351937 241618309 905829299 888111372 719238005 702960353 469709526 820884489 3444708 426257144 563923618 180027755 370742008 185090422 784960490 750846936 57863692 666100118 248434997 633406662 357619058 834975403 667767102 755139842 255418095 510568603 409596786 695898410 864204346 532395614 70313077 827039795 308952448 237611140 558167197 202864611 198562275 121438124 384489077 461365079 963229686 302632206 733081916 770664319 406644291 726544114 111224163 910952861 349799877 488113975 5184275 93630922 15136878 954541517 492542629 248524145 685119906 472002363 881827111 635157970 61321914 280877850 924579038 968778368 625880451 568729239 27642814 600274916 264617148 949549813 337136628 71035832 451510428 776145417 672476253 474922892 446017353 997100220 28409612 403696964 861764449 284151181 568881096 794603927 84748917 736204044 977422987 983653010 422558089 44097632 997322756 267863060 983059350 284494274 500975126 408441936 976132617 770497792 178032215 797391437 977275201 998425595 70922386 532282985 707051284 517628201 900696901 247937234 223464778 708744212 213436964 423129612 487126561 349909464 574545556 345299822 178989256 890353577 349760049 792075172 674654692 24475467 426279240 745120046 983360525 172006808 622711133 803178208 811187794 660693246 138783655 255333472 957155505 513279486 633865615 418271404 669617824 125517230 395627317 566435985 797650311 674793016 488755691 451787572 150142275 743057241 384778423 513211533 573494949 550769891 405856981 565481959 874662897 785490235 517436979 497456738 913591136 123683803 131834868 542890353 310050206 763760593 86690030 585251677 177944652 489849919 683654188 436772287 978870399 475023577 411447660 791707146 11680063 382206058 374096801 913696767 312890377 738530127 978247026 779920950 85052238 758128122 684973498 503230620 977668338 622645616 120356870 474404079 473982157 466958796 479395098 270819140 22237485 414037178 616608620 646384258 815957331 544004604 238780839 533215461 260693489 38063081 690640682 57726075 260770738 186969577 361333383 769516458 574443442 64175354 112050180 67500456 417835010 938367022 198620701 420738818 297554982 3862827 519781376 102667286 813345174 479071913 650354703 778926488 934390848 529364216 939224162 577216785 168099588 17566839 883427650 575257435 345741367 546974750 569937327 577767718 347634209 884901365 446650843 735375735 867773311 654028186 909211565 484496420 726901761 942991040 89946944 230216793 581967053 335493546 746922337 766447893 659976442 624496564 312055828 338064302
